package algotithm.jianzhioffer.test14;

/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/16-13:55
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int res = solution.cuttingRope(6);
        System.out.println(res);
    }

    /**
     * 用数学法是最快的
     * 当n >= 5的时候，对于某个数N，可以差分成为 3 + (n - 3),其结果为 3*(n-3) = 3n-9 = n + (2n-9) = n + 1 > n
     * 当n = 4时，拆分成为2+2，其结果不变
     * 如果有3个以上的2 ，那么 3 * 3 > 2 * 2 * 2
     * 所以这个题应当根据范围来贪心，超过4的优先使用4，剩下的全用3
     *
     * @param n 输入身子的长度
     * @return res
     */
    public int cuttingRope(int n) {
        int res = 1;
        if (n <= 3) {
            return 1 * (n - 1);
        }
        if (n % 3 == 1) {
            res = 4;
            n -= 4;
        } else if (n % 3 == 2) {
            res = 2;
            n -= 2;
        }
        while (n > 0) {
            res *= 3;
            n -= 3;
        }
        return res;
    }


    /**
     *
     * @param n 输入绳子的长度n
     * @return dp[n]
     */
//    public int cuttingRope(int n) {
//        int[] dp = new int[n+1];
//        for (int i = 2; i <= n; i++) {
//            for (int j = 1; j < i; j++) {
//                dp[i] = Math.max(dp[i],Math.max(j * (i-j),dp[i-j] * j));
//            }
//        }
//        return dp[n];
//    }


}
